Thực đơn
Tìm kiếm nhị phân
Về mặt số phép so sánh, hiệu suất của thuật toán tìm kiếm nhị phân có thể được phân tích bằng cách biểu diễn quá trình chạy thuật toán trên cây nhị phân. Nút gốc của cây là phần tử đứng giữa mảng. Phần tử đứng giữa nửa nhỏ hơn là nút con bên trái của nút gốc, và phần tử đứng giữa nửa lớn hơn là nút con bên phải của nút gốc. Phần còn lại của cây cũng được dựng như vậy. Bắt đầu từ nút gốc, tùy theo giá trị cần tìm nhỏ hơn hay lớn hơn nút đang xét mà thuật toán sẽ duyệt theo cây con bên trái hay bên phải.[6][12]
Trong trường hợp tệ nhất, thuật toán thực hiện ⌊ log 2 ( n ) + 1 ⌋ {\textstyle \lfloor \log _{2}(n)+1\rfloor } lần lặp so sánh, trong đó ⌊ ⌋ {\textstyle \lfloor \rfloor } là ký hiệu của hàm floor cho kết quả là số nguyên lớn nhất nhỏ hơn hoặc bằng giá trị bên trong, và log 2 {\textstyle \log _{2}} là phép logarit nhị phân. Nguyên nhân là do khi gặp phải trường hợp tệ nhất, thuật toán phải đi tới bậc sâu nhất trong cây, và số bậc trong cây luôn bằng ⌊ log 2 ( n ) + 1 ⌋ {\textstyle \lfloor \log _{2}(n)+1\rfloor } với bất cứ phép tìm kiếm nhị phân nào.
Trường hợp tệ nhất còn có thể xảy ra khi giá trị cần tìm không có trong mảng. Nếu n {\textstyle n} ở dạng 2 α − 1 {\textstyle 2^{\alpha }-1} thì trường hợp này luôn xảy ra. Nếu không, thuật toán có thể thực hiện ⌊ log 2 ( n ) + 1 ⌋ {\textstyle \lfloor \log _{2}(n)+1\rfloor } phép lặp nếu phải đi tới bậc sâu nhất của cây. Tuy nhiên, nếu thuật toán kết thúc ngay ở bậc sâu thứ hai của cây, quá trình tìm kiếm có thể chỉ cần thực hiện ⌊ log 2 ( n ) ⌋ {\textstyle \lfloor \log _{2}(n)\rfloor } phép lặp, ít hơn trường hợp tệ nhất một phép.[13]
Giả sử mỗi phần tử có xác suất được thực hiện tìm kiếm như nhau, trung bình thuật toán tìm kiếm nhị phân thực hiện ⌊ log 2 ( n ) ⌋ + 1 − ( 2 ⌊ log 2 ( n ) ⌋ + 1 − ⌊ log 2 ( n ) ⌋ − 2 ) / n {\displaystyle \lfloor \log _{2}(n)\rfloor +1-(2^{\lfloor \log _{2}(n)\rfloor +1}-\lfloor \log _{2}(n)\rfloor -2)/n} phép lặp khi phần tử cần tìm có mặt trong mảng, hay xấp xỉ bằng log 2 ( n ) − 1 {\displaystyle \log _{2}(n)-1} . Khi phần tử cần tìm không có trong mảng, thuật toán thực hiện trung bình ⌊ log 2 ( n ) ⌋ + 2 − 2 ⌊ log 2 ( n ) ⌋ + 1 / ( n + 1 ) {\displaystyle \lfloor \log _{2}(n)\rfloor +2-2^{\lfloor \log _{2}(n)\rfloor +1}/(n+1)} phép lặp, nếu giả sử khoảng giữa và bên ngoài các phần tử đều có xác suất được tìm như nhau.[12]
Trong trường hợp tốt nhất, khi giá trị cần tìm nằm ngay giữa mảng, vị trí của nó được trả về ngay sau một phép lặp.[14]
Về mặt số phép lặp, không có thuật toán tìm kiếm nào chỉ bằng so sánh các phần tử có thể có hiệu suất trung bình hay thậm chí trong trường hợp tệ nhất tốt hơn tìm kiếm nhị phân. Cây so sánh biểu diễn tìm kiếm nhị phân có số bậc ít nhất có thể do mọi bậc phía trên bậc thấp nhất của cây đều được lấp đầy hoàn toàn.[lower-alpha 1] Nếu không, thuật toán tìm kiếm có thể loại bỏ một vài phần tử trong mỗi phép lặp, làm tăng số phép lặp cần thực hiện trong trường hợp trung bình và tệ nhất. Các thuật toán tìm kiếm khác dùng cách so sánh đều bị rơi vào trường hợp này, do mặc dù chúng có thể chạy nhanh hơn với một số giá trị cần tìm nhất định, hiệu suất trung bình trên tất cả phần tử vẫn kém hơn tìm kiếm nhị phân. Bằng cách chia mảng thành hai nửa, thuật toán tìm kiếm nhị phân đảm bảo được kích thước của hai mảng con giống nhau nhất có thể.[15]
Thuật toán tìm kiếm nhị phân cần ba con trỏ để trỏ tới các phần tử, bất kể kích thước của mảng; đó có thể là chỉ số các phần tử trong mảng hoặc con trỏ tới địa chỉ trong bộ nhớ. Tuy nhiên, thuật toán cần ít nhất ⌈ log 2 ( n ) ⌉ {\displaystyle \left\lceil \log _{2}(n)\right\rceil } bit để mã hóa một con trỏ tới một phần tử trong mảng có n {\displaystyle n} phần tử.[16] Do đó, độ phức tạp không gian của tìm kiếm nhị phân là O ( log n ) {\displaystyle O(\log n)} . Ngoài ra, thuật toán còn cần O ( n ) {\displaystyle O(n)} không gian để lưu trữ mảng.
Số phép lặp trung bình được thực hiện bởi thuật toán tùy thuộc vào xác suất mỗi phần tử được thực hiện tìm kiếm. Trường hợp trung bình khi tìm kiếm thành công và không thành công là khác nhau. Ta giả sử mỗi phần tử có xác suất được tìm như nhau nếu tìm kiếm thành công. Nếu tìm kiếm không thành công, ta giả sử các khoảng giữa và ngoài các phần tử có xác suất được tìm giống nhau. Trường hợp trung bình khi tìm kiếm thành công là số phép lặp cần thực hiện để tìm mọi phần tử chính xác một lần, chia cho n {\displaystyle n} , số phần tử trong mảng. Trường hợp trung bình khi tìm kiếm không thành công là số phép lặp cần thực hiện để tìm một phần tử trong mọi khoảng chính xác một lần, chia cho n + 1 {\displaystyle n+1} khoảng.[12]
Khi biểu diễn bằng cây nhị phân, một lần tìm kiếm thành công có thể được biểu diễn bằng một đường đi từ gốc tới nút cần tìm, gọi là đường đi trong (internal path). Độ dài của một đường đi là số cạnh (đường nối giữa các nút) mà đường đó đi qua. Số phép lặp mà một lần tìm kiếm thực hiện, với điều kiện độ dài của đường đi tương ứng với lần tìm đó là l {\displaystyle l} , là l + 1 {\displaystyle l+1} tính cả phép lặp ban đầu. Độ dài đường đi trong (internal path length) là tổng độ dài tất cả các đường đi trong. Do chỉ có một đường đi duy nhất từ gốc tới bất cứ nút nào, mỗi đường trong đó biểu diễn cho một phép tìm kiếm phần tử tương ứng. Nếu có n {\displaystyle n} phần tử, và độ dài đường trong là I ( n ) {\displaystyle I(n)} , thì số phép lặp trung bình cho một lần tìm kiếm thành công là T ( n ) = 1 + I ( n ) n {\displaystyle T(n)=1+{\frac {I(n)}{n}}} , trong đó đã cộng thêm một bước lặp ở đầu.[12]
Do tìm kiếm nhị phân là thuật toán tối ưu cho việc tìm kiếm bằng cách so sánh, bài toán được đơn giản hóa thành việc tính độ dài đường đi trong tối thiểu của tất cả cây nhị phân có n {\displaystyle n} nút, tức là bằng:[17]
I ( n ) = ∑ k = 1 n ⌊ log 2 ( k ) ⌋ {\displaystyle I(n)=\sum _{k=1}^{n}\left\lfloor \log _{2}(k)\right\rfloor }
Ví dụ, với một mảng 7 phần tử, phần tử gốc cần một phép lặp, hai phần tử bên dưới gốc cần hai phép lặp, và bốn phần tử dưới nữa gần ba phép lặp. Trong trường hợp này, độ dài đường đi trong là:[17]
∑ k = 1 7 ⌊ log 2 ( k ) ⌋ = 0 + 2 ( 1 ) + 4 ( 2 ) = 2 + 8 = 10 {\displaystyle \sum _{k=1}^{7}\left\lfloor \log _{2}(k)\right\rfloor =0+2(1)+4(2)=2+8=10}
Số phép lặp trung bình sẽ là 1 + 10 7 = 2 3 7 {\displaystyle 1+{\frac {10}{7}}=2{\frac {3}{7}}} dựa theo công thức với trường hợp trung bình. Tổng I ( n ) {\displaystyle I(n)} có thể rút gọn thành:[15]
I ( n ) = ∑ k = 1 n ⌊ log 2 ( k ) ⌋ = ( n + 1 ) ⌊ log 2 ( n + 1 ) ⌋ − 2 ⌊ log 2 ( n + 1 ) ⌋ + 1 + 2 {\displaystyle I(n)=\sum _{k=1}^{n}\left\lfloor \log _{2}(k)\right\rfloor =(n+1)\left\lfloor \log _{2}(n+1)\right\rfloor -2^{\left\lfloor \log _{2}(n+1)\right\rfloor +1}+2}
Thay I ( n ) {\displaystyle I(n)} vào phương trình T ( n ) {\displaystyle T(n)} :[15]
T ( n ) = 1 + ( n + 1 ) ⌊ log 2 ( n + 1 ) ⌋ − 2 ⌊ log 2 ( n + 1 ) ⌋ + 1 + 2 n = ⌊ log 2 ( n ) ⌋ + 1 − ( 2 ⌊ log 2 ( n ) ⌋ + 1 − ⌊ log 2 ( n ) ⌋ − 2 ) / n {\displaystyle T(n)=1+{\frac {(n+1)\left\lfloor \log _{2}(n+1)\right\rfloor -2^{\left\lfloor \log _{2}(n+1)\right\rfloor +1}+2}{n}}=\lfloor \log _{2}(n)\rfloor +1-(2^{\lfloor \log _{2}(n)\rfloor +1}-\lfloor \log _{2}(n)\rfloor -2)/n}
Với n {\displaystyle n} là một số nguyên, phương trình trên tương đương với phương trình trong trường hợp trung bình cho một lần tìm kiếm thành công như đã chỉ ra ở trên.
Ta có thể biểu diễn lần tìm kiếm không thành công bằng cách thêm vào cây các nút ngoài, tạo thành cây nhị phân mở rộng. Nếu một nút trong, hoặc một nút có trong cây, có ít hơn hai nút con, thì ta sẽ thêm vào các nút con bổ sung, gọi là các nút ngoài, để mỗi nút trong đều có hai nút con. By doing so, an unsuccessful search can be represented as a path to an external node, whose parent is the single element that remains during the last iteration. Đường đi ngoài (external path) là đường đi từ gốc đến một nút ngoài. Độ dài đường đi ngoài (external path length) là tổng độ dài tất cả đường đi ngoài unique. Nếu số phần tử là n {\displaystyle n} ( n {\displaystyle n} là số nguyên dương), và độ dài đường đi ngoài là E ( n ) {\displaystyle E(n)} , thì số phép lặp trung bình cho một lần tìm kiếm không thành công là T ′ ( n ) = E ( n ) n + 1 {\displaystyle T'(n)={\frac {E(n)}{n+1}}} , trong đó đã tính một phép lặp lúc đầu. Trong công thức này, ta lấy độ dài đường đi ngoài chia cho n + 1 {\displaystyle n+1} chứ không phải n {\displaystyle n} vì có n + 1 {\displaystyle n+1} đường đi ngoài biểu diễn cho các khoảng giữa và ngoài các phần tử trong mảng.[15]
Tương tự, bài toán này có thể đơn giản hóa thành bài toán tính độ dài đường đi ngoài tối thiếu của tất cả cây nhị phân có n {\displaystyle n} nút. Với tất cả các cây nhị phân, độ dài đường đi ngoài bằng độ dài đường đi trong cộng với 2 n {\displaystyle 2n} .[17] Thay I ( n ) {\displaystyle I(n)} vào ta có:[15]
E ( n ) = I ( n ) + 2 n = [ ( n + 1 ) ⌊ log 2 ( n + 1 ) ⌋ − 2 ⌊ log 2 ( n + 1 ) ⌋ + 1 + 2 ] + 2 n = ( n + 1 ) ( ⌊ log 2 ( n ) ⌋ + 2 ) − 2 ⌊ log 2 ( n ) ⌋ + 1 {\displaystyle E(n)=I(n)+2n=\left[(n+1)\left\lfloor \log _{2}(n+1)\right\rfloor -2^{\left\lfloor \log _{2}(n+1)\right\rfloor +1}+2\right]+2n=(n+1)(\lfloor \log _{2}(n)\rfloor +2)-2^{\lfloor \log _{2}(n)\rfloor +1}}
Thay E ( n ) {\displaystyle E(n)} vào công thức tính T ′ ( n ) {\displaystyle T'(n)} , ta có thể xác định trường hợp trung bình cho những lần tìm kiếm không thành công:[15]
T ′ ( n ) = ( n + 1 ) ( ⌊ log 2 ( n ) ⌋ + 2 ) − 2 ⌊ log 2 ( n ) ⌋ + 1 ( n + 1 ) = ⌊ log 2 ( n ) ⌋ + 2 − 2 ⌊ log 2 ( n ) ⌋ + 1 / ( n + 1 ) {\displaystyle T'(n)={\frac {(n+1)(\lfloor \log _{2}(n)\rfloor +2)-2^{\lfloor \log _{2}(n)\rfloor +1}}{(n+1)}}=\lfloor \log _{2}(n)\rfloor +2-2^{\lfloor \log _{2}(n)\rfloor +1}/(n+1)}
Mỗi phép lặp trong cách tìm kiếm nhị phân trên thực hiện một hoặc hai lần so sánh để kiểm tra phần tử ở giữa có bằng với giá trị cần tìm không. Giả sử mỗi phần tử có xác suất được tìm bằng nhau, mỗi phép lặp thực hiện trung bình 1,5 lần so sánh. Một cách làm khác của thuật toán sẽ thực hiện kiểm tra phần tử giữa ở cuối mỗi lần tìm kiếm. Theo cách này, trung bình mỗi phép lặp bỏ qua 0,5 lần so sánh, tiết kiệm thời gian hơn một chút trên mỗi phép lặp ở hầu hết các loại máy tính. Tuy nhiên, cách này lại khiến mỗi lần tìm kiếm luôn phải thực hiện số phép lặp tối đa, trung bình mỗi lần tìm cộng thêm một phép lặp. Vì vòng lặp so sánh chỉ được thực hiện ⌊ log 2 ( n ) + 1 ⌋ {\textstyle \lfloor \log _{2}(n)+1\rfloor } lần trong trường hợp tệ nhất, the slight increase in efficiency per iteration does not compensate for the extra iteration for all but very large n {\textstyle n} .[lower-alpha 2][19][20]
Trong quá trình phân tích hiệu suất của thuật toán, một vấn đề khác cần lưu ý là thời gian cần để so sánh hai phần tử. Với các số nguyên và chuỗi ký tự, khoảng thời gian này tăng tuyến tính do độ dài mã hóa (thường là số bit) của các phần tử tăng theo. Ví dụ, một cặp số nguyên dương 64 bit sẽ cần phải so sánh số bit gấp đôi so với một cặp số nguyên dương 32 bit. Trường hợp tệ nhất được đạt đến khi hai số nguyên bằng nhau. Điều này có thể đáng lưu tâm khi độ dài mã hóa của các phần tử ở mức lớn, ví dụ như khi so sánh các số thuộc kiểu nguyên lớn hơn hay so sánh các chuỗi ký tự dài, khiến cho việc so sánh rất tốn thời gian. Hơn nữa, so với các số nguyên hoặc chuỗi ký tự ngắn thì so sánh các giá trị dấu phẩy động (cách biểu diễn số thông dụng nhất của số thực) thường còn tốn thời gian hơn..
Trên hầu hết các kiểu kiến trúc máy tính, bộ vi xử lý có bộ nhớ cache riêng tách biệt khỏi RAM. Do nằm ngay trong bộ xử lý, bộ nhớ cache có thể truy cập nhanh hơn nhưng thường chỉ chứa được ít dữ liệu hơn RAM. Do đó, hầu hết các bộ xử lý lưu địa chỉ những vùng bộ nhớ đã được truy cập gần đây và cả những vùng bộ nhớ xung quanh chúng. Ví dụ, khi truy cập vào một phần tử trong mảng, phần tử này, cùng với cả những phần tử được lưu gần đó, có thể được lưu vào trong RAM để sau đó có thể truy cập nhanh hơn được vào các phần tử khác liền kề (tính địa phương trong truy xuất - locality of reference). Với một mảng đã sắp xếp, quá trình tìm kiếm nhị phân có thể phải nhảy sang các vùng bộ nhớ nằm xa nếu mảng có kích thước lớn, không giống như các thuật toán (như tìm kiếm tuyến tính hay dò tuyến tính trong bảng băm) truy cập các phần tử theo thứ tự lần lượt. Điều này làm thời gian chạy của thuật toán tăng lên đôi chút với các mảng lớn trên hầu hết các hệ thống.[21]
Thực đơn
Tìm kiếm nhị phânLiên quan
Tài liệu tham khảo
WikiPedia: Tìm kiếm nhị phân